package _11_整理题目._3_字符串_递归_dfs_bfs_双指针._子串子序列_最值;

import org.junit.Test;

/**
 * 给定两个字符串str1和str2，输出两个字符串的最长公共子序列 Longest Common Subsequence。
 * 如果最长公共子序列为空，则返回"-1"。目前给出的数据，仅仅会存在一个最长的公共子序列
 * 子序列：字符之间可以不连续
 * 
 * 这是一道经典的二维动态规划算法题，像这种子序列的题，一般都是用动态规划
 * 
 * 动态规划：求出 s1 的前 i 个字符 和 s2 的前 j 个字符的 所有的 最长公共子序列长度
 * 1、定义 dp 和长度
 *      dp[i][j] 表示 s1 的前 i 个字符 和 s2 的前 j 个字符的 最长公共子序列长度
 *      dp[0][0] 即表示 "" 和 "" 的最长公共子序列长度，
 *      所以 dp[m][n] m = s1.length()+1  n = s2.length()+1
 * 2、边界值
 *      dp[0][0] 即表示 "" 和 "" 的最长公共子序列长度 均为 0
 *      dp[i][0] dp[0][j] 也均为 0
 * 3、转移方程：已知 dp[i][j] 之前的值，如何求 dp[i][j]
 *      如果 s1[i-1]==s2[j-1] 则 最长公共子序列长度 dp[i][j] = dp[i-1][j-1] + 1
 *      否则 dp[i][j] = Max(dp[i-1][j], dp[i][j-1])
 * 
 * 生成一个 最长公共子序列长度 的子序列并返回
 *      根据生成时的规则可知，只有在 s1[i] == s2[j] 时，才是需要的字符
 *      从最后的值往前推，两个指针 i=m  j=n
 *      当 s1[i] != s2[j] 时，如果
 * 
 */
public class _022_最长公共子序列 {
    
    public String LCS (String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m+1][n+1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i-1)==s2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        
        if(dp[m][n] == 0) return "-1";
        int i = m, j = n;
        StringBuilder sb = new StringBuilder();
        while (i>0 && j>0) {
            if (s1.charAt(i-1) == s2.charAt(j-1)) {
                sb.append(s1.charAt(i-1));
                i--;
                j--;
            } else {
                if (dp[i-1][j] > dp[i][j-1]) {
                    i--;
                } else {
                    j--;
                }
            }
        }
        
        return sb.reverse().toString();
    }
    
    @Test
    public void main() {
        String str1 = "1A2C3D4B56";
        String str2 = "B1D23A456A";
        System.out.println(LCS(str1, str2));
        assert LCS(str1, str2).equals("123456");
    }
    
}
